package com.leetcode.双周赛.第47场;

import java.util.*;

/**
 * @author: xiaomi
 * @date: 2021/3/6
 * @description: 5682. 所有子字符串美丽值之和
 * https://leetcode-cn.com/contest/biweekly-contest-47/problems/sum-of-beauty-of-all-substrings/
 */
public class B_5682_所有子字符串美丽值之和 {

    static B_5682_所有子字符串美丽值之和 action = new B_5682_所有子字符串美丽值之和();

    public static void main(String[] args) {
        test1();
        test2();
    }

    public static void test1() {
        // 5
        String s = "aabcb";
        int res = action.beautySumByForce(s);
        System.out.println("res = " + res);
    }

    public static void test2() {
        // 17
        String s = "aabcbaa";
        int res = action.beautySumByForce(s);
        System.out.println("res = " + res);
    }

    /**
     * 似乎只能用暴力了，但是第四题根本看不懂了
     * 【问题在于如何快速得出 max 和 min】
     * （我需要用什么结构来构造一个这样的结构呢？）
     * min 通过一个 set(Character 进行辅助了)
     * 想到了一个虽然也是暴力的，但是有避免重复计算的部分
     * a-z:097-122
     * ??? 好难，费了一个小时
     *
     * @param s
     * @return
     */
    public int beautySumFail(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        if (len < 3) {
            return 0;
        }
        //true -> 正序；
//        boolean flag = true;
        int[] recordArr = new int[123];
        int begin = 0, end = 2;
        //只能用这种笨方法了
        Set<Character>[] setsArr = new Set[len + 1];
        for (int i = 0; i <= len; i++) {
            setsArr[i] = new HashSet<>();
        }
        int max = 0;
        for (int i = 0; i < 3; i++) {
            int ov = recordArr[chars[i]];
            if (ov != 0) {
                //如果是新的元素
                setsArr[ov].remove(chars[i]);
            }
            int nv = ov + 1;
            max = Math.max(nv, max);
            recordArr[chars[i]] = nv;
            setsArr[nv].add(chars[i]);
        }
        int min = 1;
        for (; min <= len; min++) {
            if (!setsArr[min].isEmpty()) {
                break;
            }
        }

        //感觉这种求 max 和 min 还是有问题的。我感觉自己碰到瓶颈了。
        return -1;
    }

    /**
     * 准备用 行转列的方式 来实现，暴力破解！
     * 居然通过了！
     * @param s
     * @return
     */
    public int beautySumByForce(String s) {
        char[] chars = s.toCharArray();
        int len = chars.length;
        if (len < 3) {
            return 0;
        }
        int[] record = new int[123];
        int res = 0;
        //当 i == len-2 时不用考虑
        int limit = len - 2;
        for (int i = 0; i < limit; i++) {
            //count - set
            HashMap<Integer, Set<Character>> countSet = new HashMap<>();
            int max = 1;
            int min = 1;
            record[chars[i]]++;
            Set<Character> tempSet = new HashSet<>();
            tempSet.add(chars[i]);
            countSet.put(1, tempSet);
            for (int j = i + 1; j < len; j++) {
                if (record[chars[j]] == 0) {
                    //如果是新的元素
                    record[chars[j]] = 1;

                    countSet.get(1).add(chars[j]);
                    min = 1;
                } else {
                    int oldV = record[chars[j]];
                    int newV = oldV + 1;
                    Set<Character> oldSet = countSet.get(oldV);
                    oldSet.remove(chars[j]);
                    if (min == oldV && oldSet.isEmpty()) {
                        //如果都移除完了
                        min = newV;
                    }

                    if (!countSet.containsKey(newV)) {
                        //此时产生了 max
                        Set<Character> tempS = new HashSet<>();
                        tempS.add(chars[j]);

                        countSet.put(newV, tempS);
                        max = newV;
                    } else {
                        countSet.get(newV).add(chars[j]);
                    }
                    record[chars[j]] = newV;
                }
                //完成一次子串
                res += max - min;
            }
            //清空数组
            clearArr(record);
        }
        return res;
    }

    private void clearArr(int[] record) {
        for (int i = 97; i < 123; i++) {
            record[i] = 0;
        }
    }

    static class Item {
        int value;
        int count;

        public Item(int value, int count) {
            this.value = value;
            this.count = count;
        }
    }
}

